/*
 * 1013. 二分查找
 * 描述
 * 给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。
 * 
 * 样例
 * 在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2。
 * 
 * 挑战
 * 如果数组中的整数个数超过了2^32，你的算法是否会出错？
 * 
 * 2018.06.02 @jeyming
 */
package first_position_of_target_1014;

public class first_position_of_target_1014 {
	/**
	 * @param nums: The integer array.
	 * @param target: Target to find.
	 * @return: The first position of target. Position starts from 0.
	 */
	public static int binarySearch(int[] nums, int target) {
		// write your code here
		int low = 0, high = nums.length-1, mid;
		while(low <= high) {
			if(nums[low] == target)
				return low;
			if(nums[high] == target)
				return high;
			mid = low + (low + high)/2;
			if(nums[mid] == target)
				return mid;
			if(nums[mid] < target)
				low = mid + 1;
			else
				high = mid -1;
		}
		return -1;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// [2,2,3,4,5,6,8,13,17,18]
		// 17
		int[] nums = {1,2,3,3,4,5,10};
		int[] nums1 = {2,2,3,4,5,6,8,13,17,18};
		System.out.println(nums.length);
		System.out.println(binarySearch(nums,3));
		System.out.println(nums1.length);
		System.out.println(binarySearch(nums1,17));
	}

}
